package org.jeecg.modules.utils;

import org.jeecg.modules.entity.Order;

import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 撮合算法
 * 有序集合list，返回从小到大相加等于指定值x的所有组合
 * @author Administrator
 */
public class MultipleNumbersSum {


    public static List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();
        backtrack(nums, target, 0, 0, currentCombination, combinations);

        return combinations;
    }

    private static void backtrack(int[] nums, int target, int start, int currentSum,
                                  List<Integer> currentCombination, List<List<Integer>> combinations) {
        //当前和等于目标值，找到一个组合
        if (currentSum == target) {
            combinations.add(new ArrayList<>(currentCombination));
            return;
        }
        //当前和大于等于目标值，终止递归
        if (currentSum >= target) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            int num = nums[i];
            currentCombination.add(num);
            backtrack(nums, target, i+1, currentSum + num, currentCombination, combinations);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {100, 200, 300, 400, 500, 600};
        int target = 700;

        List<List<Integer>> combinations = findCombinations(nums, target);
        System.out.println("组合列表：");
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }

        List<Order> orders = Arrays.asList(Order.generateRandomOrder(),Order.generateRandomOrder(),Order.generateRandomOrder(),
                Order.generateRandomOrder(),Order.generateRandomOrder());
        orders.sort((x,y)-> Long.compare(x.getOcount(),y.getOcount()));
        List<List<Order>> combinations1 = findCombinations(orders, 2000);
        for (List<Order> orderList : combinations1) {
            System.out.println(orderList);
            for (Order order : orderList) {
                System.out.println(order.getOcount());
            }
        }
    }


    /**
     * 撮合算法
     * 有序集合list，返回从小到大相加等于指定值x的所有组合
     * @param orders
     * @param target
     * @return
     */
    public static List<List<Order>> findCombinations(List<Order> orders, long target) {
        List<List<Order>> combinations = new ArrayList<>();
        List<Order> currentCombination = new ArrayList<>();
        backtrack(orders, target, 0, 0, currentCombination, combinations);

        return combinations;
    }

    private static void backtrack(List<Order> orders, long target, int start, long currentSum,
                                  List<Order> currentCombination, List<List<Order>> combinations) {
        //当前和等于目标值，找到一个组合
        if (currentSum == target) {
            combinations.add(new ArrayList<>(currentCombination));
            return;
        }
        //当前和大于等于目标值，终止递归
        if (currentSum >= target) {
            return;
        }

        for (int i = start; i < orders.size(); i++) {
            long num = orders.get(i).getOcount();
            currentCombination.add(orders.get(i));
            backtrack(orders, target, i+1, currentSum + num, currentCombination, combinations);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

}
